#include "pch.h"
#include "BST.h"

void InitBSTree(BST *t) {
	t->root = NULL;
}

bool InsertBSTree(BSTNode **t, T x) {
	if (*t == NULL) {
		*t = (BSTNode*)malloc(sizeof(BSTNode));
		assert(*t != NULL);
		(*t)->data = x;
		(*t)->leftChild = (*t)->rightChild = NULL;
		return true;
	}
	else if (x < (*t)->data) {
		return InsertBSTree(&(*t)->leftChild, x);
	}
	else if (x > (*t)->data) {
		return InsertBSTree(&(*t)->rightChild, x);
	}
	return false;
}
bool InsertBSTree(BST *t, T x) {
	return InsertBSTree(&t->root, x);
}

T Min(BSTNode *t) {
	for (; t->leftChild != NULL; t = t->leftChild);
	return t->data;
}
T Min(BST *t) {
	assert(t != NULL);
	return Min(t->root);
}

T Max(BSTNode *t) {
	for (; t->rightChild != NULL; t = t->rightChild);
	return t->data;
}
T Max(BST *t) {
	assert(t != NULL);
	return Max(t->root);
}

void Sort(BSTNode *t) {
	if (t != NULL) {
		Sort(t->leftChild);
		cout << t->data;
		Sort(t->rightChild);
	}
}
void Sort(BST *t) {
	assert(t != NULL);
	Sort(t->root);
}

BSTNode* Search(BSTNode *t, T key) {
	if (t != NULL) {
		return NULL;
	}
	if (t->data == key)
		return t;
	else if (key < t->data)
		return Search(t->leftChild,key);
	else return Search(t->rightChild, key);
}
BSTNode* Search(BST *t,T key) {
	assert(t != NULL);
	return Search(t->root,key);
}

void MakeEmptyBSTree(BSTNode **t) {
	if (*t != NULL) {
		MakeEmptyBSTree(&(*t)->leftChild);
		MakeEmptyBSTree(&(*t)->rightChild);
		free(*t);
		*t = NULL;
	}
}
void MakeEmptyBSTree(BST *t) {
	assert(t != NULL);
	MakeEmptyBSTree(&t->root);
}

bool RemoveBSTree(BSTNode **t, T key) {
	if (*t == NULL)
		return false;
	if(key<(*t)->data)
		RemoveBSTree(&(*t)->leftChild,key);
	else if(key>(*t)->data)
		RemoveBSTree(&(*t)->rightChild,key);
	else {
		BSTNode *p = NULL;
		/*if ((*t)->leftChild == NULL && (*t)->rightChild == NULL) {
			free(*t);
			*t = NULL;
		}
		else if ((*t)->leftChild != NULL && (*t)->rightChild == NULL) {
			p = *t;
			*t = (*t)->leftChild;
			free(p);
			p = NULL;
		}
		else if ((*t)->leftChild == NULL && (*t)->rightChild != NULL) {
			p = *t;
			*t = (*t)->rightChild;
			free(p);
			p = NULL;
		}
		else {
			p = (*t)->rightChild;
			for (; p->leftChild != NULL; p = p->leftChild);
			(*t)->data = p->data;
			RemoveBSTree(&(*t)->rightChild, p->data);
		}*/
		if ((*t)->leftChild != NULL && (*t)->rightChild != NULL) {
			p = (*t)->rightChild;
			for (; p->leftChild != NULL; p = p->leftChild);
			(*t)->data = p->data;
			RemoveBSTree(&(*t)->rightChild, p->data);
		}
		else {
			p = *t;
			if ((*t)->leftChild == NULL)
				(*t) = (*t)->rightChild;
			if ((*t)->leftChild == NULL)
				(*t) = (*t)->leftChild;
			free(p);
			p = NULL;
		}
	}
	return true;
}
bool RemoveBSTree(BST *t,T key) {
	assert(t != NULL);
	return RemoveBSTree(&t->root,key);
}